#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

// 得到一个随机数组,长度是n,数组中每个数都在1~v之间,随机得到
vector<int> randomArray(int n, int v) {
    vector<int> arr(n);
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % v + 1;
    }
    return arr;
}

// 复制数组
vector<int> copyArray(const vector<int>& arr) {
    int n = arr.size();
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = arr[i];
    }
    return ans;
}

// 判断两个数组是否相同
bool sameArray(const vector<int>& arr1, const vector<int>& arr2) {
    int n = arr1.size();
    for (int i = 0; i < n; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}

// 数组中交换i和j位置的数
void swap(vector<int>& arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

// 选择排序
void selectionSort(vector<int>& arr) {
    if (arr.empty() || arr.size() < 2) {
        return;
    }
    for (int minIndex, i = 0; i < arr.size() - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);
    }
}

// 冒泡排序
void bubbleSort(vector<int>& arr) {
    if (arr.empty() || arr.size() < 2) {
        return;
    }
    for (int end = arr.size() - 1; end > 0; end--) {
        for (int i = 0; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }
    }
}

// 插入排序
void insertionSort(vector<int>& arr) {
    if (arr.empty() || arr.size() < 2) {
        return;
    }
    for (int i = 1; i < arr.size(); i++) {
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
}

int main() {
    // 随机数组最大长度
    int N = 200;
    // 随机数组每个值,在1~V之间等概率随机
    int V = 1000;
    // testTimes : 测试次数
    int testTimes = 50000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTimes; i++) {
        // 随机得到一个长度,长度在[0~N-1]
        int n = rand() % N;
        // 得到随机数组
        vector<int> arr = randomArray(n, V);
        vector<int> arr1 = copyArray(arr);
        vector<int> arr2 = copyArray(arr);
        vector<int> arr3 = copyArray(arr);
        selectionSort(arr1);
        bubbleSort(arr2);
        insertionSort(arr3);
        if (!sameArray(arr1, arr2) || !sameArray(arr1, arr3)) {
            cout << "出错了!" << endl;
            // 当有错了
            // 打印是什么例子,出错的
            // 打印三个功能,各自排序成了什么样
            // 可能要把例子带入,每个方法,去debug!
        }
    }
    cout << "测试结束" << endl;
    return 0;
}